import java.util.Arrays;

/**
 * Created by L.jp
 * Description:排升序
 * User: 86189
 * Date: 2021-10-22
 * Time: 21:34
 */
/*
* 时间复杂度：O（N^1.3~1.5)
* 空间复杂度：O（1），没有创建额外的空间
* 稳定性：不稳定，因为跳着分组
* */
public class ShellSort {
    public static void shellSort(int []arr){
        int gap= arr.length;
        while(gap>1){
            shell(arr,gap);
            gap=gap/2;

        }
        shell(arr,1);
    }
    public static void shell(int[]arr,int gap ){
        for (int i = gap; i < arr.length; i++) {//i++这样可以一个一个访问，不需要跳到同组的下一个元素
            int tmp=arr[i];
            int j=i-gap;//j=i-gap，找到同组元素，使得是同组元素比较
            for(;j>=0;j-=gap){
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=tmp;//有两种情况，一是arr[j]<tmp,此时i下标为空，i=j+gap,所以让arr[j+gap]=tmp;
                                      //二是 此时j<0，j+gap使得j回到数组第一个元素

        }

    }

    public static void main(String[] args) {
        int[]arr={12,2,5,6,34,33,2,56,10,13,52,11,3,30};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
